#include <iostream>
//#include <iterator>
#include <vector>
#include <set>
#include <list>
#include <fstream>
#include <map>
#include <time.h>
#include <sstream>
using namespace std;

class Node;

#define WSIZE (sizeof(unsigned)*8)

vector<Node *> gPointers;	// associative arrays storing newly added pointer-pointee pairs.
vector<Node *> gPointees;
bool gStayCool = true;
unsigned gEvalNo = 0;

#define checktime(fun, var)	{	\
	starttime = clock();		\
	fun;				\
        endtime = clock();		\
        var += endtime - starttime;	\
}


class Node {
public:
	Node(string &name) { init(name); }
	Node() { pointees.clear(); }
	~Node() {}
	void init(string &name) {
		this->name = name;
		pointees.clear();
		Node *defaultPointee = new Node();
		defaultPointee->name = name + "<mem>";
		addPointerTo(defaultPointee);
	}
	string getName() { 
		return name; 
	}
	set<Node *> &getPointees() { return pointees; }
	bool addPointerTo(Node *n) {
		if (pointees.find(n) == pointees.end()) {
			pointees.insert(n);
			gPointers.push_back(this);
			gPointees.push_back(n);
			return true;	// changed.
		} else {
			return false;	// unchanged.
		}
	}
	bool copy(Node *n);
	bool loadFrom(Node *n);
	bool storeTo(Node *n);
	void print();

private:
	set<Node *> pointees;
	string name;
};

bool Node::copy(Node *n) {
	bool changed = false;
	for (set<Node *>::iterator ii = n->pointees.begin(); ii != n->pointees.end(); ++ii) {
		changed |= addPointerTo(*ii);
	}
	return changed;
}
bool Node::loadFrom(Node *n) {
	bool changed = false;
	for (set<Node *>::iterator ii = n->pointees.begin(); ii != n->pointees.end(); ++ii) {
		changed |= this->copy(*ii);
	}
	return changed;
}
bool Node::storeTo(Node *n) {
	bool changed = false;
	for (set<Node *>::iterator ii = pointees.begin(); ii != pointees.end(); ++ii) {
		changed |= (*ii)->copy(n);
	}
	return changed;
}
void Node::print() {
	cout << getName() << ": ";
	for (set<Node *>::iterator ii = pointees.begin(); ii != pointees.end(); ++ii) {
		cout << (*ii)->getName() << ", ";
	}
	cout << "\n";
}

class Constraint {
public:
	enum ConstraintType {AddressOf, Copy, Load, Store};
	Constraint(ConstraintType ctype, Node *dst, Node *src) {
		this->ctype = ctype;
		this->dst = dst;
		this->src = src;
		this->evalno = 0;
	}
	~Constraint() {}
	void print();
	void addDependence(Constraint *to);
	bool operator == (Constraint &c);

	enum ProcessingState {NotProcessed, VisitedOnce, Visited, Processed} state;
public:
	ConstraintType ctype;
	Node *dst, *src;
	set<Constraint *> beforeme;
	unsigned evalno;
};
bool operator < (const Constraint &left, const Constraint &right) {
	if (left.ctype < right.ctype || 
	    (left.ctype == right.ctype && left.dst < right.dst) ||
	    (left.ctype == right.ctype && left.dst == right.dst && left.src < right.src) ||
	    false) {
		return true;
	}
	return false;
}

void Constraint::print() {
	if (ctype == Store) cout << '*';
	cout << dst->getName();
	cout << " = ";
	if (ctype == AddressOf) cout << '&';
	else if (ctype == Load) cout << '*';
	cout << src->getName();
	cout << '\n';
}
bool Constraint::operator == (Constraint &c) {
	if (this->ctype == c.ctype && this->dst == c.dst && this->src == c.src) {
		return true;
	}
	return false;
}
bool lessthanevalno(const Constraint &left, const Constraint &right) {
	return left.evalno < right.evalno;
}
void Constraint::addDependence(Constraint *to) {
	this->beforeme.insert(to);	// for set.
	//this->beforeme.push_back(to);	// for list.
}
class ConstraintSolver {
public:
	ConstraintSolver() {
		constraints.clear();
		nametonode.clear();
		nametoconstraint.clear();
		timeremoveaddressof = timeadddependence = timeinitconstraints = 0;
		timeaddstardependence = timesolvedependence = 0;
	
		aconstraints = NULL;
		nextconstraint = 0;
		listconstraints.clear();
	}
	~ConstraintSolver() {}

	enum ConstraintStarDependence {DependenceStar00, DependenceStar01, DependenceStar10, DependenceStar11};
	enum ConstraintDependence {DependenceNone, DependenceForward, DependenceBackward, DependenceCyclic};

	unsigned load(string &file);
	unsigned solve();
	bool solve(Constraint *cc);
	Constraint parse(string &cstr);
	Node *getNode(string &name);
	void printConstraints();
	void printPointsToGraph();
	void initConstraints();
	unsigned solveDependence();
	bool solveDependence(Constraint *cc);
	void addDependence();
	void addDependence(Constraint *ii, Constraint *jj);
	ConstraintDependence getDependence(Constraint *ii, Constraint *jj);
	ConstraintStarDependence getStarDependenceRight(Constraint *ii, Constraint *jj);
	ConstraintStarDependence getStarDependenceLeft(Constraint *ii, Constraint *jj);
	void addStarDependence();
	void addStarDependence(Constraint *cc);
	void addStarDependence(Constraint *cc, Node *src);
	void addStarDependence(Node *dst, Node *src);
	void removeAddressOf();
	void printTimes();
	unsigned removeDuplicateConstraints();
	Constraint *getConstraint(Constraint::ConstraintType ctype, Node *dst, Node *src);
	string formName(Constraint::ConstraintType ctype, Node *dst, Node *src);

	unsigned loadgen(string &cfile);
	void addConstraint(string &cstr);
	void printConstraint(unsigned c[]);
	unsigned solvegen();
	unsigned solvegen(unsigned c[]);
	bool setbit(unsigned row, unsigned col);
	bool isset(unsigned row, unsigned col);
	unsigned getmem();
private:
	vector<Constraint> constraints;
	map<string, Node *> nametonode;
	map<string, Constraint *> nametoconstraint;
	clock_t starttime, endtime;
	double timeremoveaddressof, timeadddependence;	// see initialization in constructor above.
	double timeinitconstraints, timeaddstardependence, timesolvedependence;

	unsigned **aconstraints;
	typedef set<unsigned>settype;
	vector<settype> bitmap;
	unsigned nvars, nconstraints;
	unsigned nextconstraint;
	
	list<unsigned *> listconstraints;
};
void ConstraintSolver::printTimes() {
	cout << "remove addressof = " << timeremoveaddressof/CLOCKS_PER_SEC << " sec.\n";
	cout << "add dependence = " << timeadddependence/CLOCKS_PER_SEC << " sec.\n";
	cout << "init constraints = " << timeinitconstraints/CLOCKS_PER_SEC << " sec.\n";
	cout << "add star dependence = " << timeaddstardependence/CLOCKS_PER_SEC << " sec.\n";
	cout << "solve dependence = " << timesolvedependence/CLOCKS_PER_SEC << " sec.\n";
}
unsigned ConstraintSolver::removeDuplicateConstraints() {
	unsigned nRemoved = 0;

	for (unsigned ii = 0; ii < constraints.size() - 1; ++ii) {
		for (unsigned jj = ii + 1; jj < constraints.size(); ++jj) {
			if (constraints[ii] == constraints[jj]) {
				constraints.erase(constraints.begin() + jj);
				--jj;
				++nRemoved;
			}
		}
		cout << "ii=" << ii << ".\n";
	}
	return nRemoved;
}

void ConstraintSolver::printConstraint(unsigned c[]) {
	if (c[2]) cout << "*";
	cout << "v" << c[0] << " = ";
	if (c[6]) cout << "*";
	else if (c[7]) cout << "&";
	cout << "v" << c[4] << "\n";
}
void ConstraintSolver::printConstraints() {
	/*for (vector<Constraint>::iterator ii = constraints.begin(); ii != constraints.end(); ++ii) {
		Constraint &c = *ii;
		c.print();
	}*/
	for (unsigned ii = 0; ii < nconstraints; ++ii) {
		printConstraint(aconstraints[ii]);
	}
}
void ConstraintSolver::printPointsToGraph() {
	for (map<string, Node *>::iterator ii = nametonode.begin(); ii != nametonode.end(); ++ii) {
		ii->second->print();
	}
}
Node *ConstraintSolver::getNode(string &name) {
	if (nametonode[name] == NULL) {
		Node *n = new Node(name);
		nametonode[name] = n;
	}
	return nametonode[name];
}
string ConstraintSolver::formName(Constraint::ConstraintType ctype, Node *dst, Node *src) {
	string namestr = "", ctypestr = "";

	if (ctype == Constraint::AddressOf) ctypestr = "a";
	else if (ctype == Constraint::Copy) ctypestr = "c";
	else if (ctype == Constraint::Load) ctypestr = "l";
	else if (ctype == Constraint::Store) ctypestr = "s";
	else ctypestr = "Invalid Constraint.";

	namestr = ctypestr + "-" + dst->getName() + "-" + src->getName();
	return namestr;
}
Constraint *ConstraintSolver::getConstraint(Constraint::ConstraintType ctype, Node *dst, Node *src) {
	string name = formName(ctype, dst, src);
	if (nametoconstraint[name] == NULL) {
		Constraint *c = new Constraint(ctype, dst, src);
		nametoconstraint[name] = c;
	}
	return nametoconstraint[name];
}
Constraint ConstraintSolver::parse(string &cstr) {
	//// assumptions: the constraint is well formed.
	//// i.e., no constraint of type e.g. *a = *b or &a = b is present.

	size_t eqindex = cstr.find('=');
	if (eqindex == string::npos) {
		cerr << "Error: the constraint does not contain '=': " << cstr << ".\n";
		return Constraint(Constraint::Load, NULL, NULL);
	}
	string left = cstr.substr(0, eqindex);
	string right = cstr.substr(eqindex + 1);

	size_t leftstarindex = left.find('*');
	size_t rightstarindex = right.find('*');
	if (leftstarindex != string::npos) {
		left = left.substr(leftstarindex + 1);
	}
	if (rightstarindex != string::npos) {
		right = right.substr(rightstarindex + 1);
	}

	size_t rightaddressindex = right.find('&');
	if (rightaddressindex != string::npos) {
		right = right.substr(rightaddressindex + 1);
	}
	// now you have right and left with perhaps spaces.
	size_t leftvindex = 0;
	while (left[leftvindex] == ' ') {
		++leftvindex;
	}
	size_t rightvindex = 0;
	while (right[rightvindex] == ' ') {
		++rightvindex;
	}
	size_t leftvendindex = left.size() - 1;
	while (left[leftvendindex] == ' ') {
		--leftvendindex;
	}
	size_t rightvendindex = right.size() - 1;
	while (right[rightvendindex] == ' ') {
		--rightvendindex;
	}
	// now you have right and left with spaces but end of character positions known.
	size_t leftlength = 0, rightlength = 0;

	if (leftvendindex == string::npos) {
		leftlength = string::npos;
	} else {
		leftlength = leftvendindex - leftvindex + 1;
	}
	if (rightvendindex == string::npos) {
		rightlength = string::npos;
	} else {
		rightlength = rightvendindex - rightvindex + 1;
	}

	left = left.substr(leftvindex, leftlength);
	right = right.substr(rightvindex, rightlength);

	// you got the strings without spaces and & and *.
	Constraint::ConstraintType ctype;

	if (rightaddressindex != string::npos) {
		ctype = Constraint::AddressOf;
	} else if (leftstarindex != string::npos) {
		ctype = Constraint::Store;
	} else if (rightstarindex != string::npos) {
		ctype = Constraint::Load;
	} else {
		ctype = Constraint::Copy;
	}
	Node *dst = getNode(left);
	Node *src = getNode(right);

	return *getConstraint(ctype, dst, src);
}

void ConstraintSolver::addConstraint(string &cstr) {
	unsigned left, right, dummy, isstarleft, isstarright, isaddressofright;
	sscanf(cstr.c_str(), "%d %d %d %d %d %d %d %d", &left, &dummy, &isstarleft, &dummy, &right, &dummy, &isstarright, &isaddressofright);
	/*aconstraints[nextconstraint][0] = left;
	aconstraints[nextconstraint][1] = dummy;
	aconstraints[nextconstraint][2] = isstarleft;
	aconstraints[nextconstraint][3] = dummy;
	aconstraints[nextconstraint][4] = right;
	aconstraints[nextconstraint][5] = dummy;
	aconstraints[nextconstraint][6] = isstarright;
	aconstraints[nextconstraint][7] = isaddressofright;*/
	++nextconstraint;

	unsigned *aa = new unsigned [8];
	aa[0] = left; aa[1] = dummy; aa[2] = isstarleft; aa[3] = dummy;
	aa[4] = right; aa[5] = dummy; aa[6] = isstarright; aa[7] = isaddressofright;
	listconstraints.push_back(aa);
}

unsigned ConstraintSolver::loadgen(string &file) {
	ifstream cfile(file.c_str());
	string cstr;

	getline(cfile, cstr);	// no of vars.
	getline(cfile, cstr);	// no of vars.
	sscanf(cstr.c_str(), "%d", &nvars);

	getline(cfile, cstr);	// 0.
	getline(cfile, cstr);	// no of constraints.
	sscanf(cstr.c_str(), "%d", &nconstraints);	

	/*aconstraints = new unsigned *[nconstraints];
	for (unsigned ii = 0; ii < nconstraints; ++ii) {
		aconstraints[ii] = new unsigned [8];
	}*/

	for (unsigned ii = 0; ii < nconstraints; ++ii) {
		getline(cfile, cstr);
		addConstraint(cstr);
	}
	cfile.close();

	bitmap.resize(nvars);	// each bitmap will contain max this many vars.
	for (unsigned ii = 0; ii < nvars; ++ii) {
		bitmap[ii].clear();
	}
	return nconstraints;
}
unsigned ConstraintSolver::load(string &file) {
	ifstream cfile(file.c_str());
	string cstr;
	
	getline(cfile, cstr);
	while (cfile.good()) {
		constraints.push_back(parse(cstr));
		getline(cfile, cstr);
	}
	cfile.close();

	/*sort(constraints.begin(), constraints.end());
	vector<Constraint>::iterator it = unique(constraints.begin(), constraints.end());
	constraints.erase(it, constraints.end());*/

	return constraints.size();
}
bool ConstraintSolver::solve(Constraint *cc) {
	bool changed = false;

	gPointers.clear();
	gPointees.clear();

	switch (cc->ctype) {
	case Constraint::AddressOf:	// a = &b.
		changed = cc->dst->addPointerTo(cc->src);
		break;
	case Constraint::Copy:		// a = b.
		changed = cc->dst->copy(cc->src);
		break;
	case Constraint::Load:		// a = *b.
		changed = cc->dst->loadFrom(cc->src);
		break;
	case Constraint::Store:		// *a = b.
		changed = cc->dst->storeTo(cc->src);
		break;
	default:
		cout << "Error: invalid constraint.\n";
		return false;
	}
	return changed;
}
ConstraintSolver::ConstraintStarDependence ConstraintSolver::getStarDependenceLeft(Constraint *ii, Constraint *jj) {
	// 00 means a=... and ...=a.
	// 11 means *a=... and ...=*a.
	// 10 means *a=... and ...=a.
	// 01 means a=... and ...=*a.
	if (ii->ctype != Constraint::Store && (jj->ctype == Constraint::Copy || jj->ctype == Constraint::Store))
		return DependenceStar00;
	if (ii->ctype == Constraint::Store && jj->ctype == Constraint::Load)
		return DependenceStar11;
	if (ii->ctype == Constraint::Store && (jj->ctype == Constraint::Copy || jj->ctype == Constraint::Store))
		return DependenceStar10;
	if (ii->ctype != Constraint::Store && jj->ctype == Constraint::Load)
		return DependenceStar01;
}
ConstraintSolver::ConstraintStarDependence ConstraintSolver::getStarDependenceRight(Constraint *ii, Constraint *jj) {
	// 00 means ...=a and a=....
	// 11 means ...=*a and *a=....
	// 10 means ...=*a and a=....
	// 01 means ...=a and *a=....
	if ((ii->ctype == Constraint::Copy || ii->ctype == Constraint::Store) && jj->ctype != Constraint::Store)
		return DependenceStar00;
	if (ii->ctype == Constraint::Load && jj->ctype == Constraint::Store)
		return DependenceStar11;
	if (ii->ctype == Constraint::Load && jj->ctype != Constraint::Store)
		return DependenceStar10;
	if ((ii->ctype == Constraint::Copy || ii->ctype == Constraint::Store) && jj->ctype == Constraint::Load)
		return DependenceStar01;
}
ConstraintSolver::ConstraintDependence ConstraintSolver::getDependence(Constraint *ii, Constraint *jj) {
	ConstraintStarDependence csdleft = getStarDependenceLeft(ii, jj);
	ConstraintStarDependence csdright = getStarDependenceRight(ii, jj);
	/*if (ii->dst == jj->src && jj->dst == ii->src && 
	    (csdleft == DependenceStar00 || csdleft == DependenceStar11) &&
	    (csdright == DependenceStar00 || csdright == DependenceStar11)) {
		return DependenceCyclic;
	}*/	///////// let's not bother about cycles here.
	if (ii->dst == jj->src && csdleft != DependenceStar10) return DependenceForward;
	if (jj->dst == ii->src && csdright != DependenceStar01) return DependenceBackward;
	if (ii->dst == jj->dst && ii->ctype != Constraint::Store && jj->ctype == Constraint::Store) return DependenceForward;
	if (ii->dst == jj->dst && ii->ctype == Constraint::Store && jj->ctype != Constraint::Store) return DependenceBackward;
	return DependenceNone;
}
void ConstraintSolver::addDependence(Constraint *ii, Constraint *jj) {
	ConstraintDependence cd = getDependence(ii, jj);
	switch (cd) {
	case DependenceBackward:
		ii->addDependence(jj);	// jj happens before ii.
		break;
	case DependenceForward:
		jj->addDependence(ii);
		break;
	case DependenceCyclic:
		ii->addDependence(jj);	//// not adding both ways.
		break;
	default:	// DependenceNone.
		break;
	}
}
void ConstraintSolver::addDependence() {
	for (vector<Constraint>::iterator ii = constraints.begin(); ii != constraints.end(); ++ii) {
		for (vector<Constraint>::iterator jj = ii + 1; jj != constraints.end(); ++jj) {
			addDependence(const_cast<Constraint *>(&*ii), const_cast<Constraint *>(&*jj));
		}
	}
}

unsigned ConstraintSolver::solve() {
	bool changed = false;
	unsigned niterations = 0;

	do {
		changed = false;
		for (unsigned ii = 0; ii < constraints.size(); ++ii) {
			changed |= solve(&constraints[ii]);
		}
		++niterations;
		//cout << "Iteration " << niterations << "\n";

	} while(changed);
	return niterations;
}
bool ConstraintSolver::solveDependence(Constraint *cc) {
	bool changed = false;

	switch (cc->state) {
	case Constraint::Processed:
		return changed;

	case Constraint::VisitedOnce:
	case Constraint::NotProcessed:
		if (cc->state == Constraint::NotProcessed) cc->state = Constraint::VisitedOnce;
		else if (cc->state == Constraint::VisitedOnce) cc->state = Constraint::Visited;
		for (set<Constraint *>::iterator beforemeii = cc->beforeme.begin(); beforemeii != cc->beforeme.end(); ++beforemeii) {
			changed |= solveDependence(*beforemeii);
		}
		break;

	case Constraint::Visited:
		// cycle.
		//cout << "\tcycle detected.\n";
		break;

	default:
		cout << "Error: invalid constraint state.\n";
		break;
	}
	changed |= solve(cc);
	cc->state = Constraint::Processed;
	cc->evalno = gEvalNo++;
	return changed;
}
void ConstraintSolver::initConstraints() {
	for (vector<Constraint>::iterator ii = constraints.begin(); ii != constraints.end(); ++ii) {
		ii->state = Constraint::NotProcessed;
	}
}

void ConstraintSolver::addStarDependence(Node *dst, Node *src) {
	// add dependence from ... = src to *dst = ....
	vector<Constraint *> earliers, laters;

	for (vector<Constraint>::iterator ii = constraints.begin(); ii != constraints.end(); ++ii) {
		if (ii->dst == dst && ii->ctype == Constraint::Store) {
			earliers.push_back(&*ii);
		}
		if (ii->src == src && (ii->ctype == Constraint::Copy || ii->ctype == Constraint::Store)) {
			laters.push_back(&*ii);
		}
	}
	for (vector<Constraint *>::iterator eii = earliers.begin(); eii != earliers.end(); ++eii) {
		for (vector<Constraint *>::iterator lii = laters.begin(); lii != laters.end(); ++lii) {
			(*lii)->addDependence(*eii);
		}
	}
}
void ConstraintSolver::addStarDependence(Constraint *cc, Node *src) {
	for (vector<Constraint>::iterator ii = constraints.begin(); ii != constraints.end(); ++ii) {
		if (ii->src == src && (ii->ctype == Constraint::Copy || ii->ctype == Constraint::Store)) {
			ii->addDependence(cc);
		}
	}
}
void ConstraintSolver::addStarDependence(Constraint *cc) {
	if (cc->ctype != Constraint::Store) return;

	set<Node *> &pointees = cc->dst->getPointees();
	for (set<Node *>::iterator ii = pointees.begin(); ii != pointees.end(); ++ii) {
		addStarDependence(cc, *ii);
	}
}
void ConstraintSolver::addStarDependence() {
	for (vector<Constraint>::iterator ii = constraints.begin(); ii != constraints.end(); ++ii) {
		addStarDependence(&*ii);
	}
}

void ConstraintSolver::removeAddressOf() {
	gStayCool = true;
	for (unsigned ii = 0; ii < constraints.size(); ++ii) {
		if (constraints[ii].ctype == Constraint::AddressOf) {
			solve(&constraints[ii]);
			constraints.erase(constraints.begin() + ii);
			--ii;
		}
	}
	gStayCool = false;
}

unsigned ConstraintSolver::solveDependence() {
	/*checktime(removeAddressOf(),timeremoveaddressof);
	checktime(addDependence(), timeadddependence);
	checktime(addStarDependence(), timeaddstardependence);*/

	unsigned niterations = 0;
	bool changed = false;

	/*checktime(initConstraints(), timeinitconstraints);
	for (vector<Constraint>::iterator ii = constraints.begin(); ii != constraints.end(); ++ii) {
		changed |= solveDependence(&*ii);
	}
	++niterations;
	// evalno of constraints are set.
	sort(constraints.begin(), constraints.end(), lessthanevalno);
	*/
	
	do {
		//cout << "\nIteration " << (niterations + 1) << "\n";
		changed = false;
		//checktime(initConstraints(), timeinitconstraints);
		for (vector<Constraint>::iterator ii = constraints.begin(); ii != constraints.end(); ++ii) {
			changed |= solve(&*ii);	// no solveDependence.
		}
		++niterations;
	} while (changed);
	return niterations;
}
bool ConstraintSolver::isset(unsigned row, unsigned col) {
	/*unsigned word = col/WSIZE;
	unsigned wordbit = col % WSIZE;

	unsigned andword = 1 << (WSIZE - wordbit - 1);
	return bitmap[row][word] & andword;*/
	return 0;
}
bool ConstraintSolver::setbit(unsigned row, unsigned col) {
	/*unsigned word = col/WSIZE;
	unsigned wordbit = col % WSIZE;

	unsigned orword = 1 << (WSIZE - wordbit - 1);
	unsigned ori = bitmap[row][word];
	bitmap[row][word] |= orword;
	if (ori != bitmap[row][word]) {
		return true;
	}
	return false;*/
	return 0;
}
unsigned ConstraintSolver::solvegen(unsigned c[]) {
	unsigned changed = 0;
	unsigned ori = 0;

	if (c[2]) {	// store.
		for (set<unsigned>::iterator ii = bitmap[c[0]].begin(); ii != bitmap[c[0]].end(); ++ii) {
			ori = bitmap[*ii].size();
			set_union(bitmap[*ii].begin(), bitmap[*ii].end(), bitmap[c[4]].begin(), bitmap[c[4]].end(), inserter(bitmap[*ii], bitmap[*ii].end()));
			changed += (bitmap[*ii].size() - ori);
		}
	} else if (c[6]) {	// load.
		for (set<unsigned>::iterator ii = bitmap[c[4]].begin(); ii != bitmap[c[4]].end(); ++ii) {
			ori = bitmap[c[0]].size();
			//set_union(bitmap[c[0]].begin(), bitmap[c[0]].end(), bitmap[*ii].begin(), bitmap[*ii].end(), bitmap[c[0]].end());
			set_union(bitmap[c[0]].begin(), bitmap[c[0]].end(), bitmap[*ii].begin(), bitmap[*ii].end(), inserter(bitmap[c[0]], bitmap[c[0]].end()));
			changed += (bitmap[c[0]].size() - ori);
		}
	} else if (c[7]) {	// addressof.
		ori = bitmap[c[0]].size();
		bitmap[c[0]].insert(c[4]);
		changed = (bitmap[c[0]].size() - ori);
	} else {		// copy.
		ori = bitmap[c[0]].size();
		//set_union(bitmap[c[0]].begin(), bitmap[c[0]].end(), bitmap[c[4]].begin(), bitmap[c[4]].end(), bitmap[c[0]].end());
		set_union(bitmap[c[0]].begin(), bitmap[c[0]].end(), bitmap[c[4]].begin(), bitmap[c[4]].end(), inserter(bitmap[c[0]], bitmap[c[0]].end()));
		changed = (bitmap[c[0]].size() - ori);
	}
	return changed;
}
/*unsigned ConstraintSolver::solvegen() {
    unsigned niterations = 0;
    bool changed = false;
	unsigned maxmaxsize = 0;
#define MAXVECTORSIZE 503
	vector<list<unsigned *>*> difflists(2*MAXVECTORSIZE);
	difflists[0] = &listconstraints;
	for (unsigned diffii = 1; diffii < 2*MAXVECTORSIZE; ++diffii) {
		difflists[diffii] = new list<unsigned *>;
	}

	unsigned diffentry = 0;
    do {
	cout << "iteration " << (niterations + 1) << "\n";
	changed = false;
	for (signed diffii = 2*MAXVECTORSIZE-1; diffii >= 0; --diffii) {
	//for (signed diffii = 0; diffii < 2*MAXVECTORSIZE; ++diffii) {
		bool timeschanged = false;
	    for (unsigned times = 0; times < 2; ++times) {
		list<unsigned *>::iterator ii = difflists[diffii]->begin();
		unsigned *iiend = difflists[diffii]->back();
		for (; *ii != iiend;) {
			unsigned localchanged = solvegen(*ii);
			if (localchanged >= MAXVECTORSIZE*MAXVECTORSIZE) {
				diffentry = 2*MAXVECTORSIZE - 1;	// last entry for all above diffs.
			} else {
				diffentry = localchanged / MAXVECTORSIZE;
				if (diffentry == 0) {
					diffentry = localchanged % MAXVECTORSIZE;
				} else {
					diffentry += MAXVECTORSIZE-1;
				}
			}
			// move this constraint *ii to diffentry indexed list.
			if (diffentry > diffii) {
				unsigned *iiconstraint = *ii;
				list<unsigned *>::iterator jj = ii;
				++ii;
				difflists[diffii]->erase(jj);
				difflists[diffentry]->push_back(iiconstraint);
				//cout << "\t (changed=" << localchanged << ") from " << diffii << " to " << diffentry << ": ";
				//printConstraint(iiconstraint);
			} else {
				++ii;
			}
			changed |= localchanged;
			timeschanged |= localchanged;
		}
		if (timeschanged == false) break;
	    }
	}
	++niterations;
    } while (changed);
	//cout << "nconstraints = " << nconstraints << ", maxmaxsize = " << maxmaxsize << endl;
	//cout << "last diff entry is " << 100*maxmaxsize/nconstraints << "% full." << endl;
	//for (signed diffii = 0; diffii < 2*MAXVECTORSIZE; ++diffii) {
	//	cout << "no of cons in diff[" << diffii << "] = " << difflists[diffii]->size() << endl;
	//}
    return niterations;
}*/
unsigned ConstraintSolver::solvegen() {
    unsigned niterations = 0;
    bool changed = false;
	unsigned maxmaxsize = 0;
#define MAXVECTORSIZE 203
	vector<list<unsigned *>*> difflists(MAXVECTORSIZE);
	difflists[0] = &listconstraints;
	for (unsigned diffii = 1; diffii < MAXVECTORSIZE; ++diffii) {
		difflists[diffii] = new list<unsigned *>;
	}

	unsigned diffentry = 0;
    do {
	cout << "iteration " << (niterations + 1) << "\n";
	changed = false;
	for (signed diffii = MAXVECTORSIZE-1; diffii >= 0; --diffii) {
	//for (signed diffii = 0; diffii < MAXVECTORSIZE; ++diffii) {
		bool timeschanged = false;
	    for (unsigned times = 0; times < 2; ++times) {
		list<unsigned *>::iterator ii = difflists[diffii]->begin();
		unsigned *iiend = difflists[diffii]->back();
		for (; *ii != iiend;) {
			unsigned localchanged = solvegen(*ii);
			if (localchanged >= MAXVECTORSIZE*MAXVECTORSIZE) {
				diffentry = MAXVECTORSIZE - 1;	// last entry for all above diffs.
			} else {
				diffentry = localchanged / MAXVECTORSIZE;
			}
			// move this constraint *ii to diffentry indexed list.
			if (diffentry != diffii) {
				unsigned *iiconstraint = *ii;
				list<unsigned *>::iterator jj = ii;
				++ii;
				difflists[diffii]->erase(jj);
				difflists[diffentry]->push_back(iiconstraint);
				//cout << "\t (changed=" << localchanged << ") from " << diffii << " to " << diffentry << ": ";
				//printConstraint(iiconstraint);
			} else {
				++ii;
			}
			changed |= localchanged;
			timeschanged |= localchanged;
		}
		if (timeschanged == false) break;
	    }
	}
	++niterations;
    } while (changed);
	//for (signed diffii = 0; diffii < MAXVECTORSIZE; ++diffii) {
	//	cout << "no of cons in diff[" << diffii << "] = " << difflists[diffii]->size() << endl;
	//}
    return niterations;
}
unsigned ConstraintSolver::getmem() {
	unsigned nelem = 0;
	for (vector<settype>::iterator ii = bitmap.begin(); ii != bitmap.end(); ++ii) {
		nelem += ii->size();
	}
	nelem += bitmap.size();
	return nelem*sizeof(unsigned);
}

void get_mem_usage(){
  unsigned x= 0;
  std::ifstream in("/proc/self/status");
  while(in){
    std::string line, tag;
    getline(in, line);
    std::istringstream iss(line);
    iss>>tag;
    if(tag == "VmData:"){
      iss>>x;
      break;
    }
  }
  in.close();
        std::cerr << "Memory = " << (x+512)/1024 << " MB.\n";
  return;
}


int main(int argc, char *argv[]) {
    unsigned ntotaliterations = 0;
    char *number[] = {"176", "253", "255", "252", "197", "254", "175", "186",
                      "177", "188", "300", "164", "256", "181", "183", "179"};
    for (unsigned ii = 1; ii < 2; ++ii) {
	ConstraintSolver cs;
	//string file = string("gen/spec") + number[ii] + ".gen";	/////////////////////
	if (argc != 2) {
		cout << "Usage: " << argv[0] << " <file.gen>" << endl;
		exit(1);
	}
	string file = argv[1];
	unsigned nconstraints = cs.loadgen(file);
	unsigned niterations = cs.solvegen();
	ntotaliterations += niterations;
	//cout << file << " " << nconstraints << "--------------------\n";
	cout << file << " " << niterations << "--------------------\n";
	//cout << file << " " << cs.getmem()/1000.0 << " KB\n";
	//cout << "--------------------------------------\n";
	//cs.printConstraints();
	//cs.printPointsToGraph();
	//cs.printTimes();
    }
    /*for (unsigned ii = 1; ii < 55; ++ii) {
	ConstraintSolver cs;
	char number[5];
	sprintf(number, "%d", ii);
	string file = string("g") + number + ".constraints";
	//string file = "r0.constraints";
	cs.load(file);
	unsigned niterations = cs.solveDependence();
	ntotaliterations += niterations;
	cout << niterations << "\n";
	//cout << file << " " << cs.solveDependence() << "\n";
	//cs.printConstraints();
	//cs.printPointsToGraph();
    }*/

    cout << "Total iterations: " << ntotaliterations << "\n";
	get_mem_usage();

	return 0;
}
